//#include "StdAfx.h"
#include "ActionNode.h"

//////////////////////////////////////////////////////////////////////////
//Author	:		Ross Conroy	ross.conroy@tees.ac.uk
//Date		:		02/07/2014
//
//Represents an action node of PPR representation containing; action name
//observations, parent and child nodes
//
//Update	: 24/08/2014
//Compatibility test
//////////////////////////////////////////////////////////////////////////


ActionNode::ActionNode(string nodeName, ActionNode* parent, list<string> observations)
{
	_parent = parent;
	_observations = observations;
	_nodeName = nodeName;
	_state = "";
	_occurrences = 1;
}

ActionNode::ActionNode(string nodeName, list<string> observations, string state)
{
	_parent = NULL;
	_observations = observations;
	_nodeName = nodeName;
	_state = state;
	_occurrences = 1;
}

int ActionNode::GetOcurances()
{
	return _occurrences;
}

void ActionNode::SetChildNodes(hash_map<string, ActionNode*> childNodes)
{
	_childNodes = childNodes;
}

string ActionNode::GetNodeName()
{
	return _nodeName;
}

//////////////////////////////////////////////////////////////////////////
//Used to convert node to XML
//////////////////////////////////////////////////////////////////////////
ptree ActionNode::ToXml()
{
	ptree tree;

	tree.add("Node.<xmlattr>.action", _nodeName);
	tree.add("Node.<xmlattr>.occurrences", _occurrences);

	if(_state != "")
	{
		tree.add("Node.<xmlattr>.state", _state);
	}

	if(_observations.size() > 0)
	{
		ptree& tObs = tree.add("Node.Observations","");

		for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
		{
			string observation = *it;
			ActionNode *node = _childNodes[observation];		

			if(node != NULL)
			{
				ptree& tOb = tObs.add_child("Observation", node->ToXml());
				tOb.add("<xmlattr>.observation", observation);
			}
			else
			{
				ptree& tOb = tObs.add("Observation", "");
				tOb.add("<xmlattr>.observation", observation);
			}
		}
	}	

	return tree;
}

string ActionNode::ToStringOccurrences()
{
	stringstream ss;

	for(int i = 0; i < GetNodeLevel(); i++)
	{
		ss << "\t\t";
	}

	string buff = ss.str();
	ss.clear();

	ss << "(" << _nodeName << ")";	

	ss << "[" << _occurrences << "]\n";	
	//ss << "\n";

	if(_state != "")
	{
		ss << _state << "\n"; 		
	}

	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];
		
		ss << buff << "\t<" << observation << ">\n";
		
		if(node != NULL)
		{
			ss << node->ToStringOccurrences();
		}
		else
		{
			ss << buff << "\t---\n";
		}
	}

	return ss.str();
}

string ActionNode::ToString()
{
	stringstream ss;

	for(int i = 0; i < GetNodeLevel(); i++)
	{
		ss << "\t\t";
	}

	string buff = ss.str();
	ss.clear();

	ss << "(" << _nodeName << ")";	

	//ss << "\n";

	if(_state != "")
	{
		ss << _state << "\n"; 		
	}

	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];

		ss << buff << "\t<" << observation << ">\n";

		if(node != NULL)
		{
			ss << node->ToString();
		}
		else
		{
			ss << buff << "\t---\n";
		}
	}

	return ss.str();
}

//used for outputting diagrams of trees
string ActionNode::ToTikzString(string observation, string side, int level)
{
	stringstream ss;
	string tabBuffer;

	if(level != 0)
	{
		for(int i = 0; i < level; i++)
		{
			ss << "\t";
		}
		tabBuffer = ss.str();
		ss << "node[action]{" << _nodeName << "}"  << endl;
	}
	else
	{
		ss << "\\node[action]{" << _nodeName << "}"  << endl;
	}

	//int i = 0;
	//string sides[2];
	//sides[0] = "left";
	//sides[1] = "right";

	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];
		ss << tabBuffer << "child{" << endl;
		if(node != NULL)
		{			
			ss << node->ToTikzString(observation, "left", (level + 1));			
		}
		else
		{
			ss << tabBuffer << "\tnode[empty]{}" << endl;
			ss << tabBuffer << "\tedge from parent" << endl;
			ss << tabBuffer << "\tnode[obs,auto, near end, above]{" << observation << "}" << endl;
		}
		ss <<  tabBuffer << "}" << endl;
		//i ++;
	}

	if(level != 0)
	{
		ss << tabBuffer << "edge from parent" << endl;
		ss << tabBuffer << "node[obs,auto, near end, above]{" << observation << _occurrences << "}" << endl;	
	}
	else
	{
		ss << ";" << endl;;
	}

	return ss.str();
}

//////////////////////////////////////////////////////////////////////////
//Gets what level in the tree the node is by adding 1 to its parent nodes 
//response, will return 0 when there is no parent node available as must
//be the root node if there is no parent node
//////////////////////////////////////////////////////////////////////////
int ActionNode::GetNodeLevel()
{
	if (_parent == NULL)
	{
		return 0;
	}
	else
	{
		return (_parent->GetNodeLevel() + 1);
	}
}

//////////////////////////////////////////////////////////////////////////
//Adds a child node to the action node, first check if one exists for a
//given observation, if already exists then will return false, will also
//return false if the observation does not exist in the pre-defined list
//of observations
//////////////////////////////////////////////////////////////////////////
bool ActionNode::AddChildNode(string observation, ActionNode* node)
{
	_childNodes.insert(make_pair(observation, node));
	//_childNodes[observation] = node;
	return true;
}

//////////////////////////////////////////////////////////////////////////
//Gets the length of the child tree including itself
//child tree size = max(tree size for each child) + 1
//Loops through all child nodes to find the one with the largest tree
//then adds 1 to it. If there are no children then return 1;
//////////////////////////////////////////////////////////////////////////
int ActionNode::GetChildTreeLength()
{
	int maxLength = 0;

	if (_childNodes.size() != 0)
	{
		for (hash_map<string, ActionNode*>::const_iterator it = _childNodes.begin(); it != _childNodes.end(); it++)
		{
			ActionNode * aNode = it->second;

			int l = aNode->GetChildTreeLength();
			if (l > maxLength)
			{
				maxLength = l;
			}
		}
	}

	return (maxLength + 1);
}



//////////////////////////////////////////////////////////////////////////
//Gets the child node observation pairs
//////////////////////////////////////////////////////////////////////////
hash_map<string, ActionNode*> ActionNode::GetChildNodes()
{
	return _childNodes;
}

//////////////////////////////////////////////////////////////////////////
//Gets the stored observations
//////////////////////////////////////////////////////////////////////////
list<string> ActionNode::GetObservations()
{
	return _observations;
}

void ActionNode::SetParent(ActionNode * parent)
{
	_parent = parent;
}

ActionNode * ActionNode::GetParent()
{
	return _parent;
}

string ActionNode::GetState()
{
	return _state;
}

void ActionNode::IncrementOccurrences()
{
	_occurrences++;
}

//////////////////////////////////////////////////////////////////////////
//recalculates the number of ocurances by adding the number ocurances of
//all of its child nodes
//////////////////////////////////////////////////////////////////////////
void ActionNode::CalculateOcurances()
{
	_occurrences = 0;

	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];
		if(node != NULL)
		{			
			_occurrences += node->GetOcurances();		
		}
	}

	if (_parent != NULL)
	{
		_parent->CalculateOcurances();
	}
}

//////////////////////////////////////////////////////////////////////////
//Compatibility test
//two nodes are considered compatible if the probability of each 
//observation of each branch is roughly equal as well as all potential
//child nodes having similar probabilities
//
//Compatibility Test
//Both nodes must be the same level and have the same action/name
//
//Update:	28/08/2014
//Fix compatibility test to match that in the report
//////////////////////////////////////////////////////////////////////////
bool ActionNode::IsCompatible(ActionNode * actionNode, double epsilon)
{
	bool compatible = true;

	if(this == actionNode)
	{
		compatible = false;
	}
	else if((GetNodeLevel() != actionNode->GetNodeLevel()) || (_nodeName != actionNode->GetNodeName()))
	{
		compatible = false;
	}
	//else if (actionNode->GetObservations().size() == 0 || _observations.size() == 0)
	//{
	//	//prevent counting leaves as compatible
	//	compatible = false;
	//}
	else
	{
		if(Hoeffding(actionNode, epsilon))
		{
			//If passes hoeffding test recursively test children
			for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
			{
				string observation = *it;
				ActionNode *nodeA = _childNodes[observation];
				ActionNode *nodeB = actionNode->GetChildNodes()[observation];

				if((nodeA != NULL) && (nodeB != NULL))
				{
					if (!nodeA->IsCompatible(nodeB, epsilon))
					{
						compatible = false;
					}
				}
			}
		}
		else 
		{
			compatible = false;
		}
	}
	
	return compatible;
}

//////////////////////////////////////////////////////////////////////////
//Executes the Hoeffding algorithm compared to another node
//loops through all observations and their occurrences
//
//Update 28/08/2014
//Fix to count null nodes as nodes with frequency of 0
//////////////////////////////////////////////////////////////////////////
bool ActionNode::Hoeffding(ActionNode * actionNode, double epsilon)
{
	bool hoeffding = true;

	for(list<string>::iterator it = _observations.begin(); (it != _observations.end()) && hoeffding; it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];
		ActionNode *nodeCompare = actionNode->GetChildNodes()[observation];
				
		//Hoeffding approximately equal test
		//probability = 0 when null so can still calculate comparison
		double probNode = 0;
		if(node!= NULL)
		{
			probNode = ((double)node->GetOcurances() / (double)GetTotalChildCount());
		}			
		double probCompareNode = 0;
		if(nodeCompare != NULL)
		{	
			probCompareNode = ((double)nodeCompare->GetOcurances() / (double)actionNode->GetTotalChildCount());
		}
			
		double comparison = sqrt((double)(1/(double)GetTotalChildCount()));
		comparison += sqrt((double)(1/(double)actionNode->GetTotalChildCount()));
		comparison = comparison * sqrt(0.5 * log(2.0/epsilon));

		hoeffding = (abs(probNode - probCompareNode) < comparison);
		if(!hoeffding)
		{
			return hoeffding;
		}
	}

	return hoeffding;
}

//////////////////////////////////////////////////////////////////////////
//Gets the total number of children a node has
//////////////////////////////////////////////////////////////////////////
int ActionNode::GetTotalChildCount()
{
	int childCount = 0;

	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];
		if(node != NULL)
		{			
			childCount += node->GetOcurances();		
		}
	}

	return childCount;
}

//////////////////////////////////////////////////////////////////////////
//Tests if a node has all its child noes for all observations
//////////////////////////////////////////////////////////////////////////
bool ActionNode::IsCompleteNode()
{
	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];

		//both need to be complete
		if(node == NULL)
		{
			return false;
		}
	}

	return true;
}

list<ActionNode *> ActionNode::ToListOfNodes()
{
	list<ActionNode*> nodes;
	nodes.push_back(this);

	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];

		if(node != NULL)
		{
			list<ActionNode*> tempList = node->ToListOfNodes();
			for(list<ActionNode*>::iterator itn = tempList.begin(); itn != tempList.end(); itn++)
			{
				nodes.push_back(*itn);
			}
		}
	}	

	return nodes;
}

//////////////////////////////////////////////////////////////////////////
//Merges in the missing child nodes from other node
//////////////////////////////////////////////////////////////////////////
void ActionNode::MergeMissingChildrenFromNode(ActionNode * actionNode)
{
	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];
		
		if(node == NULL)
		{
			ActionNode * mergeWithNode = actionNode->GetChildNodes()[observation];

			if(mergeWithNode != NULL)
			{
				//AddChildNode(observation, mergeWithNode);
				_childNodes[observation] = mergeWithNode;
			}
		}
	}
}

//////////////////////////////////////////////////////////////////////////
//Gets the observation that resulted in the action node
//////////////////////////////////////////////////////////////////////////
string ActionNode::GetObservationForActionNode(ActionNode * searchNode)
{
	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];
		if(node == searchNode)
		{
			return observation;
		}
	}

	return "ERROR";
}

//Returns a list of all the observations that have no action node associated
list<string> ActionNode::GetObservationsMissingActions()
{
	list<string> missing;

	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];

		//both need to be complete
		if(node == NULL)
		{
			missing.push_back(observation);
		}
	}

	return missing;
}

//returns true if any observations in the list have any actions
bool ActionNode::ContainsMissingActionsForObservations(list<string> observations)
{
	bool result = false;

	for(list<string>::iterator it = observations.begin(); it != observations.end(); it++)
	{
		string observation = *it;
		ActionNode *node = _childNodes[observation];

		//both need to be complete
		if(node != NULL)
		{
			result = true;;
		}
	}

	return result;
}


//////////////////////////////////////////////////////////////////////////
//Merges with another merge by copying its nodes where this node has a 
//missing branch
//Works recursively through child nodes calling merge on them
//merges nodes by cloning the nodes of the other node
//returns a boolean of whether or not a merge occurred
//////////////////////////////////////////////////////////////////////////
bool ActionNode::CloneMerge(ActionNode * mergeWithNode)
{
	bool merged = false;

	for(list<string>::iterator it = _observations.begin(); it != _observations.end(); it++)
	{
		string observation = *it;
		ActionNode *nodeA = _childNodes[observation];
		ActionNode *nodeB = mergeWithNode->GetChildNodes()[observation];

		//both need to be complete
		if(nodeA == NULL)
		{
			if(nodeB != NULL)
			{
				//ToDo Merge by cloning instead of pointer
				_childNodes[observation] = nodeB;
				merged = true;
			}
		}
		else if (nodeB != NULL)
		{
			if(nodeA->CloneMerge(nodeB))
			{
				merged = true;
			}
		}
	}

	return merged;
}

//Recursive compatibility test for merging
bool ActionNode::IsCompatibleWithNode(ActionNode * testNode)
{
	if (_nodeName != testNode->GetNodeName())
	{
		return false;
	}

	for (list<string>::iterator it = _observations.begin(); it!= _observations.end(); it++)
	{
		string obs = *it;

		ActionNode * childSelf = _childNodes[obs];
		ActionNode * childOther = testNode->GetChildNodes()[obs];

		if(childSelf != NULL && childOther != NULL)
		{
			if (!childSelf->IsCompatibleWithNode(childOther))
			{
				return false;
			}
		}		
	}

	return true;
}

bool ActionNode::MergeWithNode(ActionNode * testNode)
{
	if (_nodeName != testNode->GetNodeName())
	{
		return false;
	}
	else
	{
		_occurrences++;
	}

	for (list<string>::iterator it = _observations.begin(); it!= _observations.end(); it++)
	{
		string obs = *it;

		ActionNode * childSelf = _childNodes[obs];
		ActionNode * childOther = testNode->GetChildNodes()[obs];

		if(childSelf != NULL && childOther != NULL)
		{
			if (!childSelf->MergeWithNode(childOther))
			{
				return false;
			}
		}
		else if(childSelf == NULL && childOther != NULL)
		{
			childOther->SetParent(_parent);
			_childNodes[obs] = childOther;
		}
	}

	return true;
}